package leetCode.sample;

import org.junit.Test;

public class FindMedianSortedArrays {

    @Test
    public void find() {
        int[] nums1 = {1, 3};
        int[] nums2 = {2, 4, 6, 8};
        System.out.println(findMedianSortedArrays(nums1, nums2));
        System.out.println(findMedianSortedArrays2(nums1, nums2));
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length = nums1.length + nums2.length;
        int[] merge = new int[length];
        if (nums1.length == 0) {
            merge = nums2;
        } else if (nums2.length == 0) {
            merge = nums1;
        } else {
            int j = 0;
            for (int i = 0; i <= nums1.length; i++) {
                while (j < nums2.length && (i == nums1.length || nums1[i] > nums2[j])) {
                    merge[i + j] = nums2[j];
                    j++;
                }
                if (i < nums1.length) {
                    merge[i + j] = nums1[i];
                }
            }
        }
        if (length % 2 == 0) {
            return (merge[length / 2 - 1] + merge[length / 2]) / 2.0;
        } else {
            return merge[length / 2];
        }
    }

    public double findMedianSortedArrays2(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m > n) { // to ensure m<=n
            int[] temp = A;
            A = B;
            B = temp;
            int tmp = m;
            m = n;
            n = tmp;
        }
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i < iMax && B[j - 1] > A[i]) {
                iMin = i + 1; // i is too small
            } else if (i > iMin && A[i - 1] > B[j]) {
                iMax = i - 1; // i is too big
            } else { // i is perfect
                int maxLeft = 0;
                if (i == 0) {
                    maxLeft = B[j - 1];
                } else if (j == 0) {
                    maxLeft = A[i - 1];
                } else {
                    maxLeft = Math.max(A[i - 1], B[j - 1]);
                }
                if ((m + n) % 2 == 1) {
                    return maxLeft;
                }

                int minRight = 0;
                if (i == m) {
                    minRight = B[j];
                } else if (j == n) {
                    minRight = A[i];
                } else {
                    minRight = Math.min(B[j], A[i]);
                }

                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }
}
